<!-- HTML header for doxygen 1.8.6-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.13"/>
<title>OpenCV: K-Means Clustering in OpenCV</title>
<link href="../../opencv.ico" rel="shortcut icon" type="image/x-icon" />
<link href="../../tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../jquery.js"></script>
<script type="text/javascript" src="../../dynsections.js"></script>
<script type="text/javascript" src="../../tutorial-utils.js"></script>
<link href="../../search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../search/searchdata.js"></script>
<script type="text/javascript" src="../../search/search.js"></script>
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
    jax: ["input/TeX","output/HTML-CSS"],
});
//<![CDATA[
MathJax.Hub.Config(
{
  TeX: {
      Macros: {
          matTT: [ "\\[ \\left|\\begin{array}{ccc} #1 & #2 & #3\\\\ #4 & #5 & #6\\\\ #7 & #8 & #9 \\end{array}\\right| \\]", 9],
          fork: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ \\end{array} \\right.", 4],
          forkthree: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ #5 & \\mbox{#6}\\\\ \\end{array} \\right.", 6],
          forkfour: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ #5 & \\mbox{#6}\\\\ #7 & \\mbox{#8}\\\\ \\end{array} \\right.", 8],
          vecthree: ["\\begin{bmatrix} #1\\\\ #2\\\\ #3 \\end{bmatrix}", 3],
          vecthreethree: ["\\begin{bmatrix} #1 & #2 & #3\\\\ #4 & #5 & #6\\\\ #7 & #8 & #9 \\end{bmatrix}", 9],
          cameramatrix: ["#1 = \\begin{bmatrix} f_x & 0 & c_x\\\\ 0 & f_y & c_y\\\\ 0 & 0 & 1 \\end{bmatrix}", 1],
          distcoeffs: ["(k_1, k_2, p_1, p_2[, k_3[, k_4, k_5, k_6 [, s_1, s_2, s_3, s_4[, \\tau_x, \\tau_y]]]]) \\text{ of 4, 5, 8, 12 or 14 elements}"],
          distcoeffsfisheye: ["(k_1, k_2, k_3, k_4)"],
          hdotsfor: ["\\dots", 1],
          mathbbm: ["\\mathbb{#1}", 1],
          bordermatrix: ["\\matrix{#1}", 1]
      }
  }
}
);
//]]>
</script><script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js"></script>
<link href="../../doxygen.css" rel="stylesheet" type="text/css" />
<link href="../../stylesheet.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<!--#include virtual="/google-search.html"-->
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectlogo"><img alt="Logo" src="../../opencv-logo-small.png"/></td>
  <td style="padding-left: 0.5em;">
   <div id="projectname">OpenCV
   &#160;<span id="projectnumber">4.5.2</span>
   </div>
   <div id="projectbrief">Open Source Computer Vision</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.13 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "../../search",false,'Search');
</script>
<script type="text/javascript" src="../../menudata.js"></script>
<script type="text/javascript" src="../../menu.js"></script>
<script type="text/javascript">
$(function() {
  initMenu('../../',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><a class="el" href="../../d6/d00/tutorial_py_root.html">OpenCV-Python Tutorials</a></li><li class="navelem"><a class="el" href="../../d6/de2/tutorial_py_table_of_contents_ml.html">Machine Learning</a></li><li class="navelem"><a class="el" href="../../d9/d70/tutorial_py_kmeans_index.html">K-Means Clustering</a></li>  </ul>
</div>
</div><!-- top -->
<div class="header">
  <div class="headertitle">
<div class="title">K-Means Clustering in OpenCV </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><h2>Goal </h2>
<ul>
<li>Learn to use <b><a class="el" href="../../d5/d38/group__core__cluster.html#ga9a34dc06c6ec9460e90860f15bcd2f88" title="Finds centers of clusters and groups input samples around the clusters. ">cv.kmeans()</a></b> function in OpenCV for data clustering</li>
</ul>
<h2>Understanding Parameters </h2>
<h3>Input parameters</h3>
<ol type="1">
<li><b>samples</b> : It should be of <b>np.float32</b> data type, and each feature should be put in a single column.</li>
<li><b>nclusters(K)</b> : Number of clusters required at end</li>
<li><b>criteria</b> : It is the iteration termination criteria. When this criteria is satisfied, algorithm iteration stops. Actually, it should be a tuple of 3 parameters. They are `( type, max_iter, epsilon )`:<ol type="a">
<li>type of termination criteria. It has 3 flags as below:<ul>
<li><b>cv.TERM_CRITERIA_EPS</b> - stop the algorithm iteration if specified accuracy, <em>epsilon</em>, is reached.</li>
<li><b>cv.TERM_CRITERIA_MAX_ITER</b> - stop the algorithm after the specified number of iterations, <em>max_iter</em>.</li>
<li><b>cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER</b> - stop the iteration when any of the above condition is met.</li>
</ul>
</li>
<li>max_iter - An integer specifying maximum number of iterations.</li>
<li>epsilon - Required accuracy</li>
</ol>
</li>
<li><b>attempts</b> : Flag to specify the number of times the algorithm is executed using different initial labellings. The algorithm returns the labels that yield the best compactness. This compactness is returned as output.</li>
<li><b>flags</b> : This flag is used to specify how initial centers are taken. Normally two flags are used for this : <b><a class="el" href="../../d5/d38/group__core__cluster.html#gga276000efe55ee2756e0c471c7b270949a78ddd00a99cd51db10ed63c024eb1e62">cv.KMEANS_PP_CENTERS</a></b> and <b><a class="el" href="../../d5/d38/group__core__cluster.html#gga276000efe55ee2756e0c471c7b270949adfa80a38dfc0aef0de888c3164f33faf">cv.KMEANS_RANDOM_CENTERS</a></b>.</li>
</ol>
<h3>Output parameters</h3>
<ol type="1">
<li><b>compactness</b> : It is the sum of squared distance from each point to their corresponding centers.</li>
<li><b>labels</b> : This is the label array (same as 'code' in previous article) where each element marked '0', '1'.....</li>
<li><b>centers</b> : This is array of centers of clusters.</li>
</ol>
<p>Now we will see how to apply K-Means algorithm with three examples.</p>
<h2>1. Data with Only One Feature </h2>
<p>Consider, you have a set of data with only one feature, ie one-dimensional. For eg, we can take our t-shirt problem where you use only height of people to decide the size of t-shirt.</p>
<p>So we start by creating data and plot it in Matplotlib </p><div class="fragment"><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"><span class="keyword">import</span> cv2 <span class="keyword">as</span> cv</div><div class="line"><span class="keyword">from</span> matplotlib <span class="keyword">import</span> pyplot <span class="keyword">as</span> plt</div><div class="line"></div><div class="line">x = np.random.randint(25,100,25)</div><div class="line">y = np.random.randint(175,255,25)</div><div class="line">z = np.hstack((x,y))</div><div class="line">z = z.reshape((50,1))</div><div class="line">z = np.float32(z)</div><div class="line">plt.hist(z,256,[0,256]),plt.show()</div></div><!-- fragment --><p> So we have 'z' which is an array of size 50, and values ranging from 0 to 255. I have reshaped 'z' to a column vector. It will be more useful when more than one features are present. Then I made data of np.float32 type.</p>
<p>We get following image :</p>
<div class="image">
<img src="../../oc_1d_testdata.png" alt="oc_1d_testdata.png"/>
<div class="caption">
image</div></div>
<p> Now we apply the KMeans function. Before that we need to specify the criteria. My criteria is such that, whenever 10 iterations of algorithm is ran, or an accuracy of epsilon = 1.0 is reached, stop the algorithm and return the answer. </p><div class="fragment"><div class="line"><span class="comment"># Define criteria = ( type, max_iter = 10 , epsilon = 1.0 )</span></div><div class="line">criteria = (cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER, 10, 1.0)</div><div class="line"></div><div class="line"><span class="comment"># Set flags (Just to avoid line break in the code)</span></div><div class="line">flags = cv.KMEANS_RANDOM_CENTERS</div><div class="line"></div><div class="line"><span class="comment"># Apply KMeans</span></div><div class="line">compactness,labels,centers = <a class="code" href="../../d5/d38/group__core__cluster.html#ga9a34dc06c6ec9460e90860f15bcd2f88">cv.kmeans</a>(z,2,<span class="keywordtype">None</span>,criteria,10,flags)</div></div><!-- fragment --><p> This gives us the compactness, labels and centers. In this case, I got centers as 60 and 207. Labels will have the same size as that of test data where each data will be labelled as '0','1','2' etc. depending on their centroids. Now we split the data to different clusters depending on their labels. </p><div class="fragment"><div class="line">A = z[labels==0]</div><div class="line">B = z[labels==1]</div></div><!-- fragment --><p> Now we plot A in Red color and B in Blue color and their centroids in Yellow color. </p><div class="fragment"><div class="line"><span class="comment"># Now plot &#39;A&#39; in red, &#39;B&#39; in blue, &#39;centers&#39; in yellow</span></div><div class="line">plt.hist(A,256,[0,256],color = <span class="stringliteral">&#39;r&#39;)</span></div><div class="line"><span class="stringliteral">plt.hist(B,256,[0,256],color = &#39;b&#39;</span>)</div><div class="line">plt.hist(centers,32,[0,256],color = <span class="stringliteral">&#39;y&#39;</span>)</div><div class="line">plt.show()</div></div><!-- fragment --><p> Below is the output we got:</p>
<div class="image">
<img src="../../oc_1d_clustered.png" alt="oc_1d_clustered.png"/>
<div class="caption">
image</div></div>
 <h2>2. Data with Multiple Features </h2>
<p>In previous example, we took only height for t-shirt problem. Here, we will take both height and weight, ie two features.</p>
<p>Remember, in previous case, we made our data to a single column vector. Each feature is arranged in a column, while each row corresponds to an input test sample.</p>
<p>For example, in this case, we set a test data of size 50x2, which are heights and weights of 50 people. First column corresponds to height of all the 50 people and second column corresponds to their weights. First row contains two elements where first one is the height of first person and second one his weight. Similarly remaining rows corresponds to heights and weights of other people. Check image below:</p>
<div class="image">
<img src="../../oc_feature_representation.jpg" alt="oc_feature_representation.jpg"/>
<div class="caption">
image</div></div>
<p> Now I am directly moving to the code: </p><div class="fragment"><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"><span class="keyword">import</span> cv2 <span class="keyword">as</span> cv</div><div class="line"><span class="keyword">from</span> matplotlib <span class="keyword">import</span> pyplot <span class="keyword">as</span> plt</div><div class="line"></div><div class="line">X = np.random.randint(25,50,(25,2))</div><div class="line">Y = np.random.randint(60,85,(25,2))</div><div class="line">Z = np.vstack((X,Y))</div><div class="line"></div><div class="line"><span class="comment"># convert to np.float32</span></div><div class="line">Z = np.float32(Z)</div><div class="line"></div><div class="line"><span class="comment"># define criteria and apply kmeans()</span></div><div class="line">criteria = (cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER, 10, 1.0)</div><div class="line">ret,label,center=<a class="code" href="../../d5/d38/group__core__cluster.html#ga9a34dc06c6ec9460e90860f15bcd2f88">cv.kmeans</a>(Z,2,<span class="keywordtype">None</span>,criteria,10,cv.KMEANS_RANDOM_CENTERS)</div><div class="line"></div><div class="line"><span class="comment"># Now separate the data, Note the flatten()</span></div><div class="line">A = Z[label.ravel()==0]</div><div class="line">B = Z[label.ravel()==1]</div><div class="line"></div><div class="line"><span class="comment"># Plot the data</span></div><div class="line">plt.scatter(A[:,0],A[:,1])</div><div class="line">plt.scatter(B[:,0],B[:,1],c = <span class="stringliteral">&#39;r&#39;)</span></div><div class="line"><span class="stringliteral">plt.scatter(center[:,0],center[:,1],s = 80,c = &#39;y&#39;</span>, marker = <span class="stringliteral">&#39;s&#39;</span>)</div><div class="line">plt.xlabel(<span class="stringliteral">&#39;Height&#39;</span>),plt.ylabel(<span class="stringliteral">&#39;Weight&#39;</span>)</div><div class="line">plt.show()</div></div><!-- fragment --><p> Below is the output we get:</p>
<div class="image">
<img src="../../oc_2d_clustered.jpg" alt="oc_2d_clustered.jpg"/>
<div class="caption">
image</div></div>
 <h2>3. Color Quantization </h2>
<p>Color Quantization is the process of reducing number of colors in an image. One reason to do so is to reduce the memory. Sometimes, some devices may have limitation such that it can produce only limited number of colors. In those cases also, color quantization is performed. Here we use k-means clustering for color quantization.</p>
<p>There is nothing new to be explained here. There are 3 features, say, R,G,B. So we need to reshape the image to an array of Mx3 size (M is number of pixels in image). And after the clustering, we apply centroid values (it is also R,G,B) to all pixels, such that resulting image will have specified number of colors. And again we need to reshape it back to the shape of original image. Below is the code: </p><div class="fragment"><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"><span class="keyword">import</span> cv2 <span class="keyword">as</span> cv</div><div class="line"></div><div class="line">img = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(<span class="stringliteral">&#39;home.jpg&#39;</span>)</div><div class="line">Z = img.reshape((-1,3))</div><div class="line"></div><div class="line"><span class="comment"># convert to np.float32</span></div><div class="line">Z = np.float32(Z)</div><div class="line"></div><div class="line"><span class="comment"># define criteria, number of clusters(K) and apply kmeans()</span></div><div class="line">criteria = (cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER, 10, 1.0)</div><div class="line">K = 8</div><div class="line">ret,label,center=<a class="code" href="../../d5/d38/group__core__cluster.html#ga9a34dc06c6ec9460e90860f15bcd2f88">cv.kmeans</a>(Z,K,<span class="keywordtype">None</span>,criteria,10,cv.KMEANS_RANDOM_CENTERS)</div><div class="line"></div><div class="line"><span class="comment"># Now convert back into uint8, and make original image</span></div><div class="line">center = np.uint8(center)</div><div class="line">res = center[label.flatten()]</div><div class="line">res2 = res.reshape((img.shape))</div><div class="line"></div><div class="line"><a class="code" href="../../df/d24/group__highgui__opengl.html#gaae7e90aa3415c68dba22a5ff2cefc25d">cv.imshow</a>(<span class="stringliteral">&#39;res2&#39;</span>,res2)</div><div class="line"><a class="code" href="../../d7/dfc/group__highgui.html#ga5628525ad33f52eab17feebcfba38bd7">cv.waitKey</a>(0)</div><div class="line"><a class="code" href="../../d7/dfc/group__highgui.html#ga6b7fc1c1a8960438156912027b38f481">cv.destroyAllWindows</a>()</div></div><!-- fragment --><p> See the result below for K=8:</p>
<div class="image">
<img src="../../oc_color_quantization.jpg" alt="oc_color_quantization.jpg"/>
<div class="caption">
image</div></div>
 <h2>Additional Resources </h2>
<h2>Exercises </h2>
</div></div><!-- contents -->
<!-- HTML footer for doxygen 1.8.6-->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Fri Apr 2 2021 11:36:37 for OpenCV by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="../../doxygen.png" alt="doxygen"/>
</a> 1.8.13
</small></address>
<script type="text/javascript">
//<![CDATA[
addTutorialsButtons();
//]]>
</script>
</body>
</html>
